package ch2.link.single;

/**
 * 例2.14：有两个整数单链表A和B，A中的数据元素为(a0，a1，…，an-1)，B中的数据元素为(b0，b1，…，bm-1)，其中m、n均大于0。设计一个算法将A、B的所有数据结点合并起来，得到一个整数单链表C，C中的元素顺序如下：
 * C=(a0，b0， …，an-1，bn-1)				m=n
 * C=(a0，b0， …，am-1，bm-1，am，…，an-1)	m<n
 * C=(a0，b0， …，an-1，bn-1，bn，…，bm-1)	m>n
 */
public class Exam2_14 {
    public static LinkListClass<Integer> Comb(LinkListClass<Integer> A,
                                              LinkListClass<Integer> B)  {  //例2.14的算法
        LinkListClass<Integer> C = new LinkListClass<>();
        LinkNode<Integer> p, q, t;
        p = A.head.next;                    //p指向A的首结点
        q = B.head.next;                    //q指向B的首结点
        t = C.head;                         //t始终指向C的尾结点
        while (p != null && q != null) {    //当两个表均未遍历完
            t.next = p;     // 将p结点插入到C的末尾
            t = p;          // t = t.next
            p = p.next;     // p后移一个结点

            t.next = q;     // 将q结点插入到C的末尾
            t = q;          // t = t.next
            q = q.next;     // q后移一个结点
        }
        t.next = null;      //置尾结点的next为空
        if (p != null) {
            t.next = p;  // A未遍历完，将余下结点链接到C的尾部
        } else if (q != null) {
            t.next = q;  // B未遍历完，将余下结点链接到C的尾部
        }
        return C;
    }

    public static void main(String[] args) {
        Integer[] a = {1, 3, 5, 7};
        LinkListClass<Integer> A = new LinkListClass<>();
        A.CreateListR(a);
        System.out.println("A: " + A);

        Integer[] b = {1, 2, 5, 7, 9, 10, 20};
        LinkListClass<Integer> B = new LinkListClass<>();
        B.CreateListR(b);
        System.out.println("B: " + B);

        System.out.println("合并");
        LinkListClass<Integer> C = Comb(A, B);
        System.out.println("C: " + C);
        System.out.println("B: " + B);
        System.out.println("A: " + A);
    }
}

